package _12_回溯;

import java.util.ArrayList;
import java.util.List;

public class _784_字母大小写全排列 {

    // 对于排列问题，可以直接拿获得的情况，进行深度遍历
    // 对于组合问题，也可以直接拿获得的的情况进行深度遍历，但是需要注意的这一次的情况，要排除上一次情况取到的值
    public static void main(String[] args) {
        _784_字母大小写全排列 v = new _784_字母大小写全排列();
        String str = "a1b2";
        List<String> strings = v.letterCasePermutation(str);
        for (String string : strings) {
            System.out.println(string);
        }
    }

    private char[] chars;

    // 小写字母减去 - 32 等于大写字母
    public List<String> letterCasePermutation(String s) {
        chars = s.toCharArray();
        List<String> results = new ArrayList<>();
        // 字母，所对应的索引序列
        List<char[]> charList = new ArrayList<>();
        // 扫描一遍，找到所有的字母
        for (int i = 0; i < chars.length; i++) {
            if (Character.isLetter(chars[i])) {
                charList.add(new char[]{chars[i], (char) i});
            }
        }
        dfs(results, charList, 0);
        return results;
    }

    public void dfs(List<String> results, List<char[]> charList, int index) {
        if (index >= charList.size()) {
            // 越界
            results.add(new String(chars));
            return;
        }
        char[] cur = charList.get(index);
        // 大写
        char upperCase = Character.toUpperCase(cur[0]);
        chars[cur[1]] = upperCase;
        // 递归寻找值
        dfs(results, charList, index + 1);
        // 小写
        char lowerCase = (char) (upperCase + 32);
        chars[cur[1]] = lowerCase;
        dfs(results, charList, index + 1);
    }
}
